#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 3) {
            return n>2;
        }   
        int sum = 2;
        for (int i = 4; i < n; i++) {
            if ((i % 6 != 1) && (i % 6 != 5)) {
                continue;
            }
            else {
                int index = 0;
                int temp = sqrt(i);
                for (int j = 5; j <= temp; j = j + 6) {
                    if (i % j == 0 || i % (j + 2) == 0) {
                        index = 1;
                        break;
                        
                    }
                }
                if (index != 1) {
                    sum = sum + 1;
                }
            }
        }
        return sum;

    }
};

//int main() {
//    Solution S;
//    cout << S.countPrimes(10000) << endl;
//
//}